Wireless networks have become increasingly popular, as computers and other devices can be coupled for data communications without requiring wired connections between the network nodes. One set of standards for wireless networks is the IEEE 802.11 standards, but other wireless standards or protocols might be used instead. Because wireless networks are expected to operate in unfavorable conditions, such as in the presence of reflections, interference, movement of receivers/transmitters, etc., much effort is needed to correctly transmit and receive data over a wireless channel.
A typical node in a wireless network (referred to in the standards as a “station”) includes a receive chain and a transmit chain. A transmit chain typically includes some digital processing and analog circuitry (RF, baseband, etc.) that causes a signal to be transmitted into the wireless channel. A receive chain typically includes one or more antenna, RF circuitry and other analog circuitry, and digital processing that seeks to output a data stream that represents what the sending transmit chain received as its input and transmitted into the wireless network. Of course, where there are unrecoverable errors, there is a mismatch between what the sending transmit chain received and what the receiving receive chain outputs. In some cases, a receiver uses multiple antennas to improve reception of the signal from a sending transmit chain.
Because of the expected conditions, the receive chain includes various components designed to ensure that signals can be largely recovered correctly. Several techniques have been in use to recover signals. One technique is the use of MIMO (multiple-input, multiple-output) channels and another technique is the use of a maximum likelihood detector (MLD) to determine at the receiver the probabilities of what the transmitter sent and select the one or more most likely transmissions. MIMO is also used to increase bandwidth for given conditions and/or to improve reception without increased bandwidth.
In the IEEE 802.11 standards, there are at least two widely-used standards, 802.11a and 802.11b, and communication systems and devices might be required to support both standards and/or be required to operate in areas where both are being used. Enhancements to the 802.11 standards have been in place, such as the 802.11g standard that allows for OFDM transmissions (802.11a is an OFDM transmission protocol) in the 2.4 GHz band.
The 802.11a protocol supports OFDM transmissions in the 5 GHz band for data rates of 6 to 54 million bits per second (“Mbps”). The 802.11b protocol supports DSSS transmissions in the 2.4 GHz band for data rates of 1, 2, 5.5 and 11 Mbps. The 802.11g protocol mixes OFDM and DSSS protocols in the 2.4 GHz band for data rates of 1, 2, 5.5, 6, 9, 11, 12, 18, 24, 36, 48 and 54 Mbps. Data transmissions are well known for these protocols, so they need not be set forth herein. They are described, for example, in ANSI/IEEE Std 802.11, 1999 Edition; IEEE Std 802.11b, 1999; IEEE Std 802.11a, 1999/Amd 1:2000(E). Those references are incorporated by reference herein for all purposes.
MIMO systems have advantages over SISO (single-input, single-output) systems, but MIMO receivers require more processing than SISO receivers. A MIMO system comprises at least a transmitter that transmits a number of bits, or a stream of bits, over a transmission medium to a receiver. Typically, the transmission medium is a wireless radio channel but the other media such as multi-mode fiber might be used instead. A MIMO system comprises M transmit streams and N receive antennas (spatially separated, separated by polarization, or otherwise separated), where M and N are each integers greater than one (except for degenerate cases of M=1 and/or N=1, wherein MIMO techniques would work, but not provide as much benefit). Thus, an MIMO transmitter transmits its data as M streams and a receiver processes its inputs as N inputs.
A MIMO transmitter might comprise an encoder that first applies a forward error correcting (FEC) code on the bit stream that is to be received at an output of the receiver. The FEC code could be a block code, a convolution code or other code or codes. The coded bit stream is distributed by a de-multiplexer over M transmit streams. Many of the examples below use M=2 as an example, but it should be understood that the examples can be expanded to other values of M. The same is true for N, and M and N need not be the same value. In any case, the distributed, coded transmit streams are modulated and transmitted. As an example, bits for a transmit stream might be divided in groups of two bits and modulated onto a carrier using QPSK (Quaternary Phase Shift Keying) modulation, which maps the bits onto complex transmit symbols as shown in Table 1.
TABLE 1Input bit groupComplex Transmit Symbol00+1 + j · 001 0 + j · 110−1 + j · 011 0 − j · 1
More or less advanced modulation techniques are possible, such as BPSK (mapping one bit at a time), 16-QAM (mapping groups of four bits), 64-QAM (mapping groups of six bits), etc. In general, for a transmit constellation size of c, a MIMO transmitter transmits M·(log2 c) bits per symbol period, whereas a single antenna system transmits (log2 c) bits per symbol period. Herein, the transmit symbol for a particular symbol period on a transmit antenna i is denoted as xi. The transmit symbols for a symbol period can be represented as an M-dimensional vector x. These symbols are up-converted to radio frequency, transmitted and then received by N antennas at the receiver. The receiver converts the signal down to baseband frequency and, at the output of the N down-converters, N received symbols denoted as y1 through yN are available. Those received symbols can be represented by an N-dimensional vector y.
Taking into account the N×M complex channel matrix, H, and a complex noise vector n, the current received symbol vector (i.e., the symbols received in a current symbol period at the receiver) can be represented as a function of the current transmitted symbol vector as shown in Equation 1 and expanded in Equation 2. By convention, scalar values are represented herein by normal characters, vectors are represented herein by bolded lowercase characters and matrices are represented herein by uppercase bolded characters. The scalar values and the components of the vectors and matrices can be real or complex values, unless otherwise indicated.
                    y        =                  Hx          +          n                                    (                  Equ          .                                          ⁢          1                )                                          [                                                                                                                                        y                        1                                                                                                                        ⋮                                                                                                                                            y                  N                                                              ]                =                                            [                                                                                          h                      11                                                                            …                                                                              h                                              1                        ⁢                                                                                                  ⁢                        M                                                                                                                                  ⋮                                                        ⋱                                                        ⋮                                                                                                              h                                              N                        ⁢                                                                                                  ⁢                        1                                                                                                  …                                                                              h                      NM                                                                                  ]                        ⁡                          [                                                                                                                                                                        x                            1                                                                                                                                                ⋮                                                                                                                                                                                x                      M                                                                                  ]                                +                      [                                                                                                                                                        n                          1                                                                                                                                                                                                                                                                                                                                                    n                    N                                                                        ]                                              (                  Equ          .                                          ⁢          2                )            
A maximum likelihood detector (“MLD”) can be used with an FEC decoder to decode transmissions. A detector might provide hard decisions (in the case of a detector with hard decision outputs) or soft decisions (in the case of a soft decision output detector) to an FEC decoder, which would then perform the inverse of what an encoder did to the data prior to transmission and, when there are no unrecoverable errors, the FEC decoder outputs what was input to the encoder.
The detector combines received symbols and either estimates the transmitted bits to provide a hard decision (e.g., a “1” or a “0”) or produces a soft decision value for each transmitted bit representing a measure for the probability that the transmitted bit is “1” (or “0”). By quantizing the soft decision values, the soft decision detector is reduced to a hard decision detector.
Suppose a hard-decision detector operates over a MIMO channel characterized by (M, N, c), i.e., a MIMO system with M transmit antennas (possibly comprising polarizations), N receive antennas (possibly comprising polarizations) and a constellation of size c. Assume that the receiver has learned H. Typically, packets are preceded by a known training waveform that can be used by the receiver to estimate H to within some estimation accuracy. Other techniques for estimating H in packet-based communication are possible. For non-packet-based communication, mid-ambles and other techniques to estimate H exist.
The vector, {circumflex over (x)}, representing the most likely transmit vector x given what was received, can be represented as shown in Equation 3, wherein where X is the set (of size cM) of all possible transmit vectors x.
                              x          ︵                =                  arg          ⁡                      (                                          min                                  x                  ∈                  X                                            ⁢                                                                y                  -                  Hx                                                                      )                                              (                  Equ          .                                          ⁢          3                )            
Thus, the detector finds the most probably transmitted transmit vector x by finding the valid transmit vector that is “closest” to the received symbol vector y given the known channel characteristics from H. In order to find {circumflex over (x)}, the distance of received symbols from all possible received symbols, shown by the expression in Equation 4, is calculated for all x.d[x]=∥y−Hx∥  (Equ. 4)
Once the most probably transmitted transmit vector is found, the receiver can output that as a hard decision for each of the bits of the transmit vector. Since each element of x is chosen from a set of c possible constellation values, the expression of Equation 4 needs to be evaluated cM times to determine the most probably transmitted transmit vector. Thus, computational complexity for determining the most probably transmitted transmit vector grows exponentially (proportional to cM) with the number of transmit antennas (M), thus for larger values of c and M, the number of operations and calculations to decode the symbols represented by the vector x becomes prohibitive.
Herein, computational complexity refers to a measure of the computational effort required to arrive at a result, usually measurable by some combination of the number of operations needed to be performed for each calculation and the number of calculations needed (actually or on average) to reach the result. The operations can be software operations or hardware operations, or a combination, such as real or complex, fixed point or floating point, additions or multiplications. Computational complexity could correspond to the number of operations needed for computing a result, such as the average number of additions and multiplications needed. Computational complexity can be reduced by reducing the number of operations needed for each calculation or the nature of the operations (e.g., replacing a multiplication with an addition reduces complexity). Computational complexity can also be reduced by reducing the number of calculations needed. As explained in examples herein, if the expression of Equation 4 can be evaluated fewer than cM times, computational complexity will be reduced from the case where the expression is evaluated cM times even if the number of operations needed for each evaluation does not change. In addition, if the number of operations needed for each evaluation is reduced, computational complexity will be reduced further. Computational complexity can also be reduced by simplifying the individual operations, such as multiplying lower resolution values relative to the increased computational complexity of multiplying higher resolution values.
While a hard decision detector indicates its best guess for each bit of the transmit vector, a soft decision detector determines, for each bit of the transmitted transmit vector, a measure for the probability (the so-called log-likelihood ratio) that the transmitted bit was a “1” (or “0”), or does so for a collection of bits. The soft decision values provided by the soft decision detector can be quantized to reduce the result to hard decisions, or some other processing can be done to collectively reduce the result to hard decisions, such as using a trellis decoder.
For a soft decision detector, where the transmit vector contains C=M·(log2 c) bits, designated by b1 . . . bC, the detector might find soft values for each bit bj according to Equation 5, where L(bi) represents the probability that b1 was “1” at the transmitter and σ2 is the power of the noise added on each antenna E{ni*ni}, where n1, . . . , nN, are stochastic variables with Gaussian distribution as introduced in Equation 2.
                              L          ⁡                      (                          b              i                        )                          =                  log          ⁡                      (                                                            ∑                                                            x                      ❘                                              b                        i                                                              =                    1                                                  ⁢                                  exp                  ⁡                                      (                                          -                                                                                                                                                              y                              -                              Hx                                                                                                            2                                                                          σ                          2                                                                                      )                                                                                                ∑                                                            x                      ❘                                              b                        i                                                              =                                          -                      1                                                                      ⁢                                  exp                  ⁡                                      (                                          -                                                                                                                                                              y                              -                              Hx                                                                                                            2                                                                          σ                          2                                                                                      )                                                                        )                                              (                  Equ          .                                          ⁢          5                )            
The expression of Equation 5 can be approximated by the expression of Equation 6.
                              L          ⁡                      (                          b              i                        )                          ≈                              σ                          -              2                                ·                      (                                                            min                                                            x                      ❘                                              b                        i                                                              =                                          -                      1                                                                      ⁢                                                                                                y                      -                      Hx                                                                            2                                            -                                                min                                                            x                      ❘                                              b                        i                                                              =                                          +                      1                                                                      ⁢                                                                                                y                      -                      Hx                                                                            2                                                      )                                              (                  Equ          .                                          ⁢          6                )            
For soft decision decoding, the distance expression d[x]=∥y−Hx∥ also has to be evaluated for all x. Since each element of x is from a constellation with c possible values, the expression is evaluated cM times. The soft decision values are found by finding a number of minima over sub-arrays of the array d[x]. There are 2B minima for xi to be found if there are B bits in the xi constellation. Again, this can be a difficult computation for some values of c and M.
It is possible to reduce computational complexity by modifying searches over all x. For example, in one approach, 2cM−1 distance metrics are evaluated instead of CM distance metrics using a subset search processes described in U.S. Pat. No. 7,245,666 [U.S. patent application Ser. No. 10/408,015 filed on Apr. 3, 2003 and entitled “Soft Symbol Decoding for MIMO Communication Systems with Reduced Search Complexity”], which is incorporated by reference herein for all purposes. As an illustration of such a complexity reduction by reducing the number of required distance metric calculations using a subset search process, the receiver might perform using program instructions for the subset search process described by the following pseudocode:
for (all x1, x2, ..., xM−1) beginz = HM*y − HM*HM−1 xM−1 ... − HM*H1x1xM = S(HM*HM, z)d[x1, x2, ..., xM−1] = ∥ y − Hx ∥end
In that pseudocode, S(t, z) denotes the slicing operation, with a grid spacing equal (or proportional) to t. The grid spacing is used to either divide z by t, after which it is compared to a set of fixed constellation thresholds, or alternatively, to multiply the constellation thresholds by t.
The soft values for all bits can be computed from the distance values d[x1, x2, . . . , XM−1], except the bits in transmit symbol XM. To obtain the soft values for the bits in XM, the above process is repeated, but with a symbol other than XM excluded from the loop. The soft values for XM can be obtained from d[x2, x3, . . . , XM] calculated in the second pass of the subset search process.
The above methods have in common that the computational complexity is dominated by the calculations (cM, 2cM, 2cM−1 times, respectively) of d[x]. Simplifying calculation of d[x] further would reduce the computational complexity of determining the soft values.
One approach to dealing with decoding complications in MIMO systems is the use of tree detection. For example, see Vaton, S., Chonavel, T., Saoudi, S., “Approximate and Exact ML Detectors for CDMA and MIMO Systems: A Tree Detection Approach”, MMT '02 Workshop on Multiaccess, Mobility and Teletraffic for Wireless Communications, Rennes, France, Jun. 3-5, 2002 [available at http://perso-info.enst-bretagne.fr/˜vaton/mmt.ps] (hereinafter “Vaton”), which describes an exact ML detection technique with a computational complexity roughly equivalent to that of the decorrelator at usual SNRs for CDMA systems operation. Detection comprises two steps: (i) first, a QR decomposition of the matrix of users' signatures is performed for multi-user detection and (ii) the detection is performed as an optimal path selection in a tree diagram.
Vaton thus proposes QR preprocessing for maximum likelihood detection, wherein QR decomposition can be used to transform the MLD equations in a form that allows a tree formulation of the detection problem. It then discusses how two known tree search algorithms can be used to find a solution close to the optimal (“maximum likelihood, or “ML”) solution. The only possible exact detector is an exhaustive search of the tree, which needs to evaluate the metric on all branches of the tree, so at best this approach finds an optimal solution and might not reduce computational complexity.
QR decomposition (sometimes referred to as “QR factorization”) is a well-known technique and can be used to transform a channel matrix into an upper triangular matrix. In particular, a QR decomposition can be applied to the channel matrix H to find a matrix R such that H=QR and R is upper triangular. For a 2×3 matrix, for example, representing a MIMO system with M=2 transmit antennas and N=3 receive antennas, H can be factored as shown in Equation 7, where the diagonal elements of R (r11, r22, . . . ) are real numbers, and Q is a unitary matrix, i.e., Q*, the conjugate transpose of Q, is equal to its inverse: Q*Q=I.
                              [                                                                      h                  11                                                                              h                  12                                                                                                      h                  21                                                                              h                  22                                                                                                      h                  31                                                                              h                  32                                                              ]                =                              [                                                                                q                    11                                                                                        q                    12                                                                                        q                    13                                                                                                                    q                    21                                                                                        q                    22                                                                                        q                    23                                                                                                                    q                    31                                                                                        q                    32                                                                                        q                    33                                                                        ]                    ⁡                      [                                                                                r                    11                                                                                        r                    12                                                                                                0                                                                      r                    22                                                                                                0                                                  0                                                      ]                                              (                  Equ          .                                          ⁢          7                )            
Because Q is unitary, R can be found by multiplying the conjugate transpose Q* by H. In geometrical terms, Q* rotates the vectors H1 and H2 such that H2 is in the xy-plane and H1 lies along the x-axis.
A MIMO detection process referred to as V-BLAST uses QR decomposition and provides a lower computational complexity than ML detection, but at the price of a lower performance. An example of such a decoding process would involve factoring H into Q and R and then searching over all possible combinations of the input symbols. Since V-BLAST selects input symbols one-by-one, this can be a source of inaccuracy that might need to be addressed in receiver designs.